"""
有一个单向链表，链表中有可能出现“环”，如下这样。

                1 <- 8
                ↓    ↑
5 -> 3 -> 7 ->  2 -> 6

那么，
    1.如何用程序来判断该链表是否为有环链表呢？  -> 是
    2.如果链表有环，如何求出环的长度？  -> 4
    3.如果链表有环，如何求出入环节点？  -> 2
"""


class Node:
    """简易链表"""

    def __init__(self, data):
        self.data = data
        self.next = None


def is_cycle(head):
    """判断链表是否为环链表
    双指针大法 时间复杂度O(n)，空间复杂度O(1)
    """
    p1 = head
    p2 = head
    while p2 is not None and p2.next is not None:
        p1 = p1.next
        p2 = p2.next.next
        if p1 == p2:
            return True
    return False


def cycle_length(head):
    """
    当两个指针首次相遇，证明链表有环的时候，让两个指针从相遇点继续循环前进，
    并统计前进的循环次数，直到两个指针第2次相遇。
    此时，统计出来的前进次数就是环长。

    因为指针 p1 每次走1步，指针 p2 每次走2步，两者的速度差是1步。
    当两个指针再次相遇时，p2 比 p1 多走了整整1圈。
    因此，环长 = 每一次速度差 × 前进次数 = 前进次数。
    """
    p1 = head
    p2 = head
    i = 0
    length = 0
    while p2 is not None and p2.next is not None:
        p1 = p1.next
        p2 = p2.next.next
        if i == 1:
            length += 1
        if p1 == p2:
            i += 1
            if i == 2:
                return length


def cycle_node(head):
    """
    假设从链表头节点到入环点的距离是D，
    从入环点到两个指针首次相遇点的距离是S1，
    从首次相遇点回到入环点的距离是S2。
    那么，当两个指针首次相遇时，各自所走的距离是多少呢？

    指针 p1 一次只走 1 步，所走的距离是 D + S1。
    指针 p2 一次走 2 步，多走了 n（n>=1） 整圈，所走的距离是 D + S1 + n(S1 + S2)。
    由于 p2 的速度是 p1 的 2 倍，所以所走距离也是 p1 的 2 倍，因此：
    2(D + S1) = D + S1 + n(S1 + S2)
    等式经过整理得出：
    D = (n - 1)(S1 + S2) + S2

    也就是说，从链表头节点到入环点的距离，等于从首次相遇点绕环 n-1 圈再回到入环点的距离。
    这样一来，只要把其中一个指针放回到头节点位置，另一个指针保持在首次相遇点，两个指针都是每次向前走1
    步。那么，它们最终相遇的节点，就是入环节点。
    """
    p1 = head
    p2 = head
    flag = True
    while p2 is not None and p2.next is not None:
        if flag:
            p1 = p1.next
            p2 = p2.next.next
        p1 = p1.next
        p2 = p2.next
        if p1 == p2 and flag:
            flag = False
            p2 = head
        elif p1 == p2 and not flag:
            return p1.data


if __name__ == '__main__':
    node1 = Node(5)
    node2 = Node(3)
    node3 = Node(7)
    node4 = Node(2)
    node5 = Node(6)
    node6 = Node(8)
    node7 = Node(1)

    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = node6
    node6.next = node7
    node7.next = node4

    print(is_cycle(node1))
    print(cycle_length(node1))
    print(cycle_node(node1))
